package com.wxweven.algorithm.array;

import java.util.HashSet;
import java.util.Set;

class LC219存在重复元素II {

    /*
     * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
     *
     *  
     *
     * 示例 1:
     *
     * 输入: nums = [1,2,3,1], k = 3
     * 输出: true
     * 示例 2:
     *
     * 输入: nums = [1,0,1,1], k = 1
     * 输出: true
     * 示例 3:
     *
     * 输入: nums = [1,2,3,1,2,3], k = 2
     * 输出: false
     *
     * 视频讲解：https://www.youtube.com/watch?v=tWdMNboG-gI&list=PLTNkreZiUTIL-S_VJBLRxlmGktAQtla-m&index=22
     *
     */

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        // 双重循环的代码，时间复杂度较高
        // for(int i=0;i<nums.length;i++){
        //     for(int j=i+1;j<=i+k && j<nums.length;j++){
        //         if(nums[j]==nums[i]){
        //             return true;
        //         }
        //     }
        // }

        // return false;

        // 利用map的解法，时间复杂度O(n)，空间复杂度O(n)
        // Map<Integer, Integer> map = new HashMap<>();

        // for(int i=0;i<nums.length;i++){
        //     Integer index = map.get(nums[i]);
        //     if(index!=null && i-index<=k){
        //         return true;
        //     }

        //     map.put(nums[i],i);
        // }

        // return false;

        // 滑动窗口的解法，HashSet，只存k个元素
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            if (set.contains(num)) {
                return true;
            }

            set.add(num);

            // if (set.size() > k) 和 if(i >= k) 是等价的
            // if (set.size() > k) {
            if (i >= k) {
                set.remove(nums[i - k]);
            }
        }

        return false;
    }
}